#define HEADSIZ 128
#define FREESIZ (512-HEADSIZ)
#define NFREEPG (FREESIZ/sizeof(uint64))
#define BUCKETBEG (HEADSIZ+FREESIZ)
#define PGNO_INVALID 0
#define PGNO_HEAD 0
#define DEF_BUCKETS 3
#define DEF_PAGESIZ 512
//#define DEF_PSHIFT 9
#define DEF_MINKEY 2
#define DEF_LEVEL 2
#define DEF_ALIGN 4
#define HASH_MAGIC 0x12345678
struct hparam{
   int bnum;
   int pgsiz;
   int minkey;
   int align;
   int cache_maxbytes;
   int cache_nbucket;
   int swapratio;
};
struct data{
    uint32 vsiz;
    int32 maxsiz;
	char *val;
};
struct record{
   uint32 ksiz;
   uint32 vsiz;
   uint32 totsiz;
   char *key;
   char *val;
};
enum{
   PUT_REPLACE=0,
   PUT_APPEND=1,
   PUT_KEEP=2,
   //PUT_ADDINT=3,
   //PUT_ADDDOUBLE=4,
};
struct hdbhead{
   uint32 magic;
   int32 fd;
   uint64 maxpg;
   uint32 bnum;
   uint32 pgsiz;
   uint16 minkey;
   int32 flag;
   int32 align;
#define DB_RDONLY 2
#define DB_RDWR 3
   uint64 nrec;
   int64 fpgbeg;
   int32 fstart;
   int32 fend;
   int32 fnum;
   uint64 flast;
   uint64 fread;
   int32 nfpg;
   uint64 lsn;
};
struct hdb{
   struct hdbhead *head;
#define Maxpg head->maxpg
#define Bnum head->bnum
#define Pgsiz head->pgsiz
#define Minkey head->minkey
#define Fend head->fend
#define Fstart head->fstart
#define Fnum head->fnum
#define Flast head->flast
#define Fread head->fread
#define Nfpg head->nfpg
#define Align head->align
#define Lsn head->lsn
#define Fd head->fd
#define Nrec head->nrec
   uint64 *buckets;
   struct pgstack *pstack;
   uint16 oversiz;
   int flag;
#define HDB_IN_TRANSACTION 1
   struct cache *cc;
   uint64 *fpa;
   int *clock;
   char *dname;
   FILE *fp;
   struct stack *newpgno;
   struct stack *delpgno;
   int dpgs;
   pthread_rwlock_t *block;
   pthread_mutex_t dblock;
   
   //double locatetime;
   //double plocatetime;
   //double llocatetime;
   //double cmptime;
   //double puttime;
   //int locatenum;
   //int cmpnum;
};
struct idx{
   uint32 ksiz;
   uint32 vsiz;
#define PK_OFLOW 0x10000
#define V_OFLOW  0x20000
#define I_DELETED 0x40000
#define I_FLAGMASK 0xffff0000
#define I_NPADMASK (~I_FLAGMASK)
   uint32 fap;//flag and pad siz
   uint64 pgno;
   char d[1];
};
#define PAD(len) (((len)+db->Align-1)&(~(db->Align-1)))//total length
//#define PADSIZ(len) (db->align-((len)&(db->align-1)))//pad length
#define PADSIZ(len) (PAD(len)-(len))
#define SIZEOFIDX (sizeof(uint32)+sizeof(uint32)+sizeof(uint32)+sizeof(uint64))
#define NPIDXSIZ(ksiz,vsiz) (SIZEOFIDX+(ksiz)+(vsiz))
#define IDXSIZ(ksiz,vsiz) (SIZEOFIDX+PAD((ksiz)+(vsiz)))
#define IDXKSIZ(ksiz) (SIZEOFIDX+(ksiz)+sizeof(uint64))
#define NPIDXKSIZ(ksiz) (SIZEOFIDX+sizeof(uint64)+(ksiz))
#define INDEXBEG (sizeof(uint64)+sizeof(uint16)+sizeof(uint16))
struct page{
    uint64 left;
	uint16 lower;
	uint16 upper;
	uint16 index[1];
};
struct leaf{
    uint16 lower;
	uint16 upper;
	uint16 index[1];
};
#define LEAFIDXBEG (sizeof(uint16)+sizeof(uint16))
#define ISLEAF(pgno) ((pgno)&1)
#define LEAFPGNO(pgno) ((pgno)|1)
#define PGNO(pgno) ((pgno)&~1)
#define RECBEG (sizeof(uint16)+sizeof(uint16))
struct rcd{
   uint32 ksiz;
   uint32 vsiz;
   uint32 fap;//flag and pad siz
   char d[1];
};
#define SIZEOFREC (sizeof(uint32)+sizeof(uint32)+sizeof(uint32))
#define RECSIZ(ksiz,vsiz) (SIZEOFREC+PAD((ksiz)+(vsiz)))
#define RECKSIZ(ksiz) (SIZEOFREC+(ksiz)+sizeof(uint64))
struct pcursor{
   uint64 pgno;
   int16 idxoff;
};
struct pgstack{
   uint32 pnum;
   uint32 pmax;
   struct pcursor *stack;
};
struct overflowpage{
    uint64 nextpg;
	int32 siz;
	char d[1];
};
#define OFLOWHEAD (sizeof(uint64)+sizeof(uint32))
struct iterator{
    struct hdb *db;
	int clock;
    int32 bucket;
	struct pgstack pstack;
	uint16 flag;
	struct bstring *key;
#define IT_FORWORD  0
#define IT_BACKWORD 1
#define IT_BEGIN    2
#define IT_END      4
};
#define WRITEIDX(idx,ksize,vsize,fp,pg)\
    do{\
	    (idx)->ksiz=(ksize);\
		(idx)->vsiz=(vsize);\
		(idx)->fap=(uint32)(fp);\
		(idx)->pgno=(uint64)(pg);\
    }while(false)
#define RECOVERSIZ (db->oversiz-sizeof(uint64))
#define WRITEREC(rec,ksize,vsize,fp)\
    do{\
	    (rec)->ksiz=(ksize);\
		(rec)->vsiz=(vsize);\
		(rec)->fap=(fp);\
	}while(false)
#define RECTOIDX(rec,rsiz,pageno,index)\
    do{\
	    (index)->ksiz=(rec)->ksiz;\
		(index)->vsiz=(rec)->vsiz;\
		(index)->fap=(rec)->fap;\
		(index)->pgno=(pageno);\
		memcpy((index)->d,(rec)->d,(rsiz)-SIZEOFREC);\
	}while(false)
#define IDXTOREC(index,isiz,rec)\
    do{\
	    (rec)->ksiz=(index)->ksiz;\
		(rec)->vsiz=(index)->vsiz;\
		(rec)->fap=(index)->fap;\
		memcpy((rec)->d,(index)->d,(isiz)-SIZEOFIDX);\
	}while(false)
#define STACKPUSH(pstack,pageno,indexoff)\
    do{\
		if((pstack)->pnum>=(pstack)->pmax){\
		    (pstack)->pmax<<=1;\
		    (pstack)->stack=(struct pcursor*)realloc((pstack)->stack,(pstack)->pmax*sizeof(struct pcursor));\
		}\
		(pstack)->stack[(pstack)->pnum].pgno=(pageno);\
		(pstack)->stack[(pstack)->pnum].idxoff=(indexoff);\
		(pstack)->pnum++;\
    }while(false)
#define STACKPOP(pstack,pageno,indexoff)\
    do{\
	    if((pstack)->pnum>0){\
		    (pstack)->pnum--;\
	        (pageno)=(pstack)->stack[(pstack)->pnum].pgno;\
			(indexoff)=(pstack)->stack[(pstack)->pnum].idxoff;\
		}\
	}while(false)
inline static int sizeofidx(struct hdb *db,struct idx *index){
    uint32 flag=index->fap&I_FLAGMASK&~I_DELETED;
	switch(flag){
	    case PK_OFLOW:return db->oversiz;
		case V_OFLOW:return index->ksiz+sizeof(uint64)+SIZEOFIDX;
		default:return index->ksiz+index->vsiz+SIZEOFIDX;
	}
}
inline static int padidx(struct hdb *db,struct idx *index){
    uint32 flag=index->fap&I_FLAGMASK&~I_DELETED;
	switch(flag){
	   case 0:return index->ksiz+index->vsiz+(index->fap&I_NPADMASK)+SIZEOFIDX;
	   case V_OFLOW:return (index->fap&I_NPADMASK)+index->ksiz+sizeof(uint64)+SIZEOFIDX;
	   case PK_OFLOW:return db->oversiz;
	   default :return 0;
	}
}
inline static int sizeofrec(struct hdb *db,struct rcd* rec){
    uint32 flag=rec->fap&I_FLAGMASK;
	switch(flag){
	    case PK_OFLOW:return db->oversiz-sizeof(uint64);
		case V_OFLOW:return rec->ksiz+sizeof(uint64)+SIZEOFREC;
		case 0:return rec->ksiz+rec->vsiz+(rec->fap&I_NPADMASK)+SIZEOFREC;
		default:return 0;
	}
}
int delrecord(struct hdb *db,struct leaf *lf,int16 ipos);
int delindex(struct hdb *db,struct page *p,int16 ipos);
int appendrec(struct hdb* db,struct leaf *lf,char *key,int ksiz,char *val,int vsiz,uint32 hv);
int appendval(struct hdb *db,struct page *p,char *key,int ksiz,char *val,int vsiz,uint32 hv);
int getidxval(struct hdb *db,struct idx *index,char *val,int siz);
int getrecval(struct hdb *db,struct rcd *rec,char *val,int siz);
int dbread(struct hdb *db,char *buf,int len,uint64 offset);
int dbwrite(struct hdb *db,char *buf,int len,uint64 offset);
int shrinkpage(struct hdb *db);

int hdbclose(struct hdb *db);
struct hdb* hdbopen(char *filename,int flag,struct hparam *param);
bool hdbput(struct hdb *db,char *key,int ksiz,char *val,int vsiz,int flag);
int hdberase(struct hdb *db,char *key,int ksiz);
int hdbget(struct hdb *db,char *key,int ksiz,char *buf,int *bsiz);
struct bstring* hdbgetstr(struct hdb *db,struct bstring *key);
int iter_next(struct iterator* it,struct bstring **key,struct bstring **val);
struct iterator* iter_create(struct hdb* db);
int iterdel(struct iterator *it);
int hdbdelete(struct hdb *db);
#define HDBNREC(db) (db)->Nrec
#define HDBSWAPTIMES(db) (db)->cc->swaptimes
void htraver(struct hdb *db);

int hdbtrans_beg(struct hdb *db);
int hdbtrans_commit(struct hdb *db);
int hdbtrans_abort(struct hdb *db);
int hdbtrans_cancel(struct hdb *db);
